﻿package binarytree;

import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;

import javax.print.attribute.HashAttributeSet;

import common.BTNode;

public class 二叉树的序列化和反序列化 {

	/**
	 * 利用先序遍历实现二叉树的序列化和反序列化 每一个节点结束的时候加一个! 如果一个节点为null，则加上#!
	 */
	public static String serialByPreOrder(BTNode root) {
		if (root == null) {
			return "#!";
		}
		String res = root.value + "!";
		res += serialByPreOrder(root.left);
		res += serialByPreOrder(root.right);
		return res;
	}

	public static BTNode reconByPreString(String preStr) {
		String[] values = preStr.split("!");
		Queue<String> queue = new LinkedList<String>();
		for (int i = 0; i < queue.size(); i++) {
			queue.offer(values[i]);
		}
		return reconByPreString(queue);
	}

	/**
	 * 递归调用的方法
	 * 
	 * @param queue
	 * @return
	 */
	private static BTNode reconByPreString(Queue<String> queue) {
		String value = queue.poll();
		if (value.equals("#")) {
			return null;
		}
		BTNode root = new BTNode(Integer.valueOf(value));
		root.left = reconByPreString(queue);
		root.right = reconByPreString(queue);
		return root;
	}

	/**
	 * 用一个辅助的队列来实现对二叉树的按层遍历
	 * @param root
	 * @return
	 */
	public static String serialByLevelString(BTNode root) {
		if (root == null) {
			return "#!";
		}
		String res= root.value +"!";
		Queue<BTNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()){
			root = queue.poll();
			if(root.left!=null){
				res += root.left.value +"!";
				queue.offer(root.left);
			}else{
				res +="#!";
			}
			if(root.right!=null){
				res+=root.right.right +"!";
				queue.offer(root.right);
			}else{
				res +="#!";
			}
		}
		return res;
	}
	
	public static BTNode reconByLevelSerial(String value){
		String[] values = value.split("!");
		int index= 0;
		Queue<BTNode> queue = new LinkedList<>();
		BTNode root = generateBodeByString(values[index]);
		queue.offer(root);
		BTNode node =null;
		while(!queue.isEmpty()){
			node = queue.poll();
			BTNode left = generateBodeByString(values[++index]);
			node.left =left;
			if(left!=null){
				queue.offer(left);
			}
			BTNode right = generateBodeByString(values[++index]);
			node.right = right;
			if(right!=null){
				queue.offer(right);
			}			
		}
		return root;
	}

	/**
	 * 根据value来生成一个节点
	 * @param value
	 * @return
	 */
	public static BTNode generateBodeByString(String value){
		if(value.equals("#")){
			return null;
		}
		return  new BTNode(Integer.valueOf(value));
	}
}
